#include <iostream>
#include "next.h"
using namespace std;
void getNext(string p, int * next)
{
    next[0] = -1;
    int i = 0, j = -1;

    while (i < p.length())
    {
        if (j == -1 || p[i] == p[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}
int KMP(string t, string p,int* next)
{
    int i = 0;
    int j = 0;

    while (i < t.length() && j < p.length())
    {
        if (j == -1 || t[i] == p[j])
        {
            i++;
            j++;
        }
        else
            j = next[j];
    }

    if (j == p.length())
        return i - j;
    else
        return -1;
}
int main()
{
    string target = "ABABABABCA";
    string pattern = "AAAABAAAAC";
    int patten_size = pattern.length();
    vector<int> a = vector<int>(patten_size+1);
    next(pattern,a);
    for(auto i:a)
        cout<<i<<" ";

}

